4081. Частые значения - 2

Задана последовательность n целых чисел a₁ , a₂ , ... , a_n в неубывающем порядке. Вам также заданы несколько запросов, состоящих из индексов i и j (1 ≤ i ≤ j ≤ n). Для каждого запроса определите число, которое чаще всего встречается среди a_i , ... , a_j.

Вход. Состоит из нескольких тестов. Каждый тест начинается со строки, содержащей два целых числа n и q (1 ≤ n, q ≤ 500000). Следующая строка содержит n целых чисел a₁ , ... , a_n (-500000 ≤ a_i ≤ 500000, для каждого i Î {1, ..., n}), разделенных пробелом. Считайте, что для каждого i Î {1, ..., n – 1}: a_i ≤ a_i₊₁. Каждая из следующих q строк содержит один запрос, состоящий из двух целых значений i и j (1 ≤ i ≤ j ≤ n) – границы индексов запроса.

За последним тестом следует строка, содержащая один 0.

Выход. Для каждого запроса выведите одно целое число: количество вхождений чаще всего встречаемого числа в заданном интервале.

Пример входа

Пример выхода

10 3

-1 -1 1 1 1 1 3 10 10 10

2 3

1 10

5 10

РЕШЕНИЕ

структуры данных – RMQ

Анализ алгоритма

Данная задача отличается от 3838 (частые значения) увеличением ограничений по n и q, а также набором тестов, на котором решение с использованием дерева отрезков даст Time Limit.

Поскольку входная последовательность задается сразу и никогда не меняется (отсутствуют операции update), то задачу можно решить при помощи структуры Range Maximum Query. Ее преимущество состоит в том, что запрос на отрезке выполняется за константное время, а не за логарифмическое как на дереве отрезков. Итого:

· время работы решения при помощи дерева отрезков: O(n + q log₂n).

· время работы решения при помощи RMQ: O(n log₂n + q).

Отметим также, что используемая память составит:

· O(n) для дерева отрезков

· O(n log₂n) для RMQ

Чтобы свести указанную задачу к RMQ, создадим по входной последовательности новый массив b: b[i] содержит количество повторов числа a_i вплоть до индекса i. Например, если a = (3, 3, 5, 9, 9, 9, 9, 10, 10), то b = (1, 2, 1, 1, 2, 3, 4, 1, 2).

Ответ на требуемый запрос q(i, j) совершим следующим образом:

· если a_i = a_j, то ответом будет значение j – i + 1;

· иначе ищем самый правый индекс k, для которого a_i = a_k. После чего находим максимальное значение на отрезке b[k + 1, …, j], то есть RMQ_k_+1,j (для удобства вычислений Range Maximum Query будет возвращать не индекс с максимальным элементом, а сам максимальный элемент). Тогда ответом на запрос будет

max (k – i + 1, RMQ_k_+1,j).

Пример

Входной массив а:

Соответствующий ему массив b:

Рассмотрим запрос q(4, 9). Тогда k = 6 (a₄ = a₆, a₄ ≠ a₇). Ответ равен

max (k – i + 1, RMQ_k_+1,j) = max (6 – 4 + 1, RMQ_7,9) = max (3, 2) = 3

Рассмотрим запрос q(2, 5). Тогда k = 2 (a₂ = a₂, a₂ ≠ a₃). Ответ равен

max (k – i + 1, RMQ_k_+1,j) = max (2 – 2 + 1, RMQ_3,5) = max (1, 3) = 3

Реализация алгоритма

Объявим необходимые константы. Входная последовательность хранится в массиве а. Объявим вспомогательный массив b. Массив mas будет использоваться под структуру RMQ: mas[i][j] содержит максимальный элемент на отрезке [i, …, i + 2^j]. Массив mas хранит не индексы последовательности, а сами максимальные значения на отрезках. Таким образом мы избавимся от большого числа операций индексации.

#define MAX 500010

#define LOGMAX 19

int a[MAX], b[MAX];

int mas[MAX][LOGMAX];

По массиву b строим массив mas, для которого mas[i][j] = max(b_i, b_i₊₁, …, b_i_+2^j).

void Build_RMQ_Array(int *b)

{

int i, j;

for (i = 1; i <= n; i++) mas[i][0] = b[i];

for (j = 1; 1 << j <= n; j++)

for (i = 1; i + (1 << j) - 1 <= n; i++)

mas[i][j] = max(mas[i][j - 1], mas[i + (1 << (j - 1))][j - 1]);

}

Функция RMQ возвращает максимум на отрезке (b_i, b_i₊₁, …, b_j) за O(1).

int RMQ(int i, int j)

{

int k = 0;

while ((1 << (k + 1)) <= j - i + 1) k++;

return max(mas[i][k],mas[j - (1<<k) + 1][k]);

}

Основная часть программы. Читаем входной массив а. Одновременно строим по нему массив b.

while(scanf("%d %d",&n,&q), n)

{

scanf("%d",&a[1]); b[1] = 1;

for(i = 2; i <= n; i++)

{

scanf("%d",&a[i]);

if (a[i] == a[i-1]) b[i] = b[i-1] + 1; else b[i] = 1;

}

Строим структуру данных RMQ.

Build_RMQ_Array(b);

Последовательно обрабатываем запросы.

for(i = 0; i < q; i++)

{

scanf("%d %d",&Left,&Right);

if (a[Left] == a[Right]) printf("%d\n",Right - Left + 1);

else

{

LeftEnd равно самому правому индексу, для которого a_i = a_LeftEnd.

int LeftEnd =

(int)(upper_bound(a+Left,a+Right,a[Left]) - a) - 1;

res = max(LeftEnd - Left + 1, RMQ(LeftEnd + 1, Right));

printf("%d\n",res);

}

Реализация собственного бинарного поиска

В два раза быстрее чем с использованием upper_bound

#include <stdio.h>

#define MAX 500010

#define LOGMAX 19

int a[MAX], b[MAX];

int mas[MAX][LOGMAX];

int n, q, i, j, Left, Right, res;

int max(int i, int j)

{

return (i > j) ? i : j;

}

void Build_RMQ_Array(int *b)

{

int i, j;

for (i = 1; i <= n; i++) mas[i][0] = b[i];

for (j = 1; 1 << j <= n; j++)

for (i = 1; i + (1 << j) - 1 <= n; i++)

mas[i][j] = max(mas[i][j - 1], mas[i + (1 << (j - 1))][j - 1]);

}

int RMQ(int i, int j)

{

int k = 0;

while ((1 << (k + 1)) <= j - i + 1) k++;

return max(mas[i][k],mas[j - (1<<k) + 1][k]);

}

int BinSearch(int Left, int Right)

{

if (a[Left] == a[Right]) return Right;

while(Right - Left > 1)

{

int Mid = (Left + Right) / 2;

if (a[Mid] == a[Left]) Left = Mid; else Right = Mid;

}

if (a[Left] == a[Right]) return Right; else return Right - 1;

}

int main(void)

{

while(scanf("%d %d",&n,&q), n)

{

scanf("%d",&a[1]); b[1] = 1;

for(i = 2; i <= n; i++)

{

scanf("%d",&a[i]);

if (a[i] == a[i-1]) b[i] = b[i-1] + 1; else b[i] = 1;

}

Build_RMQ_Array(b);

for(i = 0; i < q; i++)

{

scanf("%d %d",&Left,&Right);

if (a[Left] == a[Right]) printf("%d\n",Right - Left + 1);

else

{

int LeftEnd = BinSearch(Left,Right);

res = max(LeftEnd - Left + 1, RMQ(LeftEnd + 1, Right));

printf("%d\n",res);

}

return 0;

}

Java реализация

import java.util.*;

import java.io.*;

class FastScanner

{

private BufferedReader br;

private StringTokenizer st;

public FastScanner(InputStreamReader reader)

{

br = new BufferedReader(reader);

}

public String next()

{

while (st == null || !st.hasMoreTokens())

{

try

{

st = new StringTokenizer(br.readLine());

} catch (Exception e)

{

e.printStackTrace();

}

return st.nextToken();

}

public int nextInt()

{

return Integer.parseInt(next());

}

public void close() throws Exception

{

br.close();

}

public class Main

{

static int a[];

static int b[];

static int mas[][];

static int max(int a, int b)

{

return (a > b) ? a : b;

}

static int BinSearch(int Left, int Right)

{

if (a[Left] == a[Right]) return Right;

while(Right - Left > 1)

{

int Mid = (Left + Right) / 2;

if (a[Mid] == a[Left]) Left = Mid; else Right = Mid;

}

if (a[Left] == a[Right]) return Right; else return Right - 1;

}

static void Build_RMQ_Array(int[] b, int n)

{

int i, j;

int logn = (int)(Math.log(n+1) / Math.log(2)) + 1;

mas = null; mas = new int[n+1][logn];

for (i = 1; i <= n; i++) mas[i][0] = b[i];

for (j = 1; 1 << j <= n; j++)

for (i = 1; i + (1 << j) - 1 <= n; i++)

mas[i][j] =

max(mas[i][j - 1], mas[i + (1 << (j - 1))][j - 1]);

}

static int RMQ(int i, int j)

{

int k = 0;

while ((1 << (k + 1)) <= j - i + 1) k++;

return max(mas[i][k],mas[j - (1<<k) + 1][k]);

}

public static void main(String[] args) throws Exception

{

FastScanner con =

new FastScanner(new InputStreamReader(System.in));

PrintWriter out = new PrintWriter(System.out);

while(true)

{

int n = con.nextInt();

if (n == 0) break;

int q = con.nextInt();

a = null; a = new int[n+1]; a[1] = con.nextInt();

b = null; b = new int[n+1]; b[1] = 1;

for(int i = 2; i <= n; i++)

{

a[i] = con.nextInt();

if (a[i] == a[i-1]) b[i] = b[i-1] + 1; else b[i] = 1;

}

Build_RMQ_Array(b,n);

for(int i = 0; i < q; i++)

{

int Left = con.nextInt();

int Right = con.nextInt();

if (a[Left] == a[Right]) out.println(Right - Left + 1);

else

{

int LeftEnd = BinSearch(Left,Right);

int res = max(LeftEnd - Left + 1, RMQ(LeftEnd + 1, Right));

out.println(res);

}

con.close();

out.close();

}